GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Boyer-Moore-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Boyer-Moore-Algorithmus</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Der Boyer-Moore-Algorithmus ist ein <a href="String-Matching-Algorithmus" title="String-Matching-Algorithmus">String-Matching-Algorithmus</a>. Der Algorithmus wird dazu genutzt, um in einem Text T einen bestimmten Teiltext (Muster M) zu finden und wurde <a href="1977" title="1977">1977</a> von <a href="Robert_S._Boyer" title="Robert S. Boyer">Robert S. Boyer</a> und <a href="J_Strother_Moore" title="J Strother Moore">J Strother Moore</a> entwickelt.

<div class="mw-heading mw-heading2"><h2 id="Algorithmus">Algorithmus</h2></div>

Das Muster wird am Anfang linksbündig unter den Text geschrieben und dann von rechts nach links Zeichen für Zeichen mit dem Text verglichen. Sobald ein Mismatch auftritt, berechnen zwei <a href="Heuristik#Informatik" title="Heuristik">Heuristiken</a>, wie weit das Suchmuster nach rechts verschoben werden kann.

<dl><dt>Bad-Character-Heuristik</dt>

<dd>Stimmt beim Vergleich des Musters mit dem Text von rechts nach links ein Zeichen des Musters nicht mit dem Zeichen des Textes überein (Bad-Character), wird im Muster nach dem letzten Vorkommen dieses Bad-Characters gesucht und das Muster so weit verschoben, bis beide Buchstaben übereinander liegen. Existiert dieser Bad-Character nicht im Muster, wird das Muster soweit verschoben, dass sein erstes Zeichen unter dem Nachfolger des Bad-Character liegt. Es kann vorkommen, dass die Bad-Character-Heuristik eine Verschiebung des Musters nach links vorschlägt. In diesem Fall wird um eine Position nach rechts geschoben.</dd>

<dt>Good-Suffix-Heuristik</dt>

<dd>Stimmt beim Vergleich des Musters mit dem Text von rechts nach links ein <a href="Suffix" title="Suffix">Suffix</a> des Musters mit dem Text überein und tritt danach aber ein Mismatch auf, wird das Muster so weit nach rechts geschoben, bis ein Teilwort des Musters wieder auf das Suffix passt. Existiert das Suffix kein zweites Mal im Muster, wird das Muster um seine volle Länge nach rechts verschoben.</dd></dl>

Es kommt vor, dass die beiden Heuristiken unterschiedliche Verschiebungen berechnen. Der Algorithmus wählt immer das <a href="Gr%C3%B6%C3%9Ftes_und_kleinstes_Element" title="Größtes und kleinstes Element">Maximum</a> der beiden Vorschläge, um das Muster nach rechts zu verschieben.

Um das Vorgehen effizient zu gestalten, wird für beide Heuristiken in einem Vorverarbeitungsschritt jeweils eine Sprungtabelle errechnet. Die Sprungtabelle für die Bad-Character-Heuristik enthält für jedes im Suchmuster vorkommende Zeichen den Abstand von der Position des letzten Vorkommens im Suchmuster bis zum Ende des Suchmusters. Die Tabelle für die Good-Suffix-Heuristik enthält für jedes Teilmuster (von hinten aus gesehen) den Abstand vom Ende des Musters, ab dem es wieder im Muster vorkommt.

<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Bad-Character-Heuristik">Bad-Character-Heuristik</h3></div>

String: Hoola-Hoola girls like Hooligans

Suchmuster: Hooligan

<pre>Hoola-Hoola girls like Hooligans

Hooligan

</pre>

Das letzte Zeichen stimmt nicht mit dem letzten des Suchmusters überein, also kann man das Suchmuster bis zum ersten „o“ (des Suchmusters, von hinten gelesen) verschieben:

<pre>Hoola-Hoola girls like Hooligans

Hooligan

Hooligan

</pre>

Das letzte Zeichen des Suchmusters stimmt nicht mit dem Text überein. An der betreffenden Stelle steht ein „g“, das sich wiederum im Muster an der dritten Position von rechts findet. Wird das Muster um zwei Zeichen nach rechts verschoben, dann „matchen“ die blauen „g“:

<pre>Hoola-Hoola girls like Hooligans

Hooligan

Hooligan

</pre>

Das „r“ im String kommt im Muster überhaupt nicht vor. Das ermöglicht – weil bereits der erste verglichene Buchstabe (von hinten) nicht passt – das Verschieben um die komplette Länge des Suchstrings, da hier ausgeschlossen ist, dass das Muster an einer Stelle matcht. Das Gleiche passiert gleich im nächsten Schritt erneut, nur ist es jetzt das Leerzeichen (statt dem „r“), das nicht im Muster vorkommt.

<pre>Hoola-Hoola girls like Hooligans

Hooligan

Hooligan

Hooligan

</pre>

Danach wurde das Muster gefunden.

Ein weiteres Beispiel, bei dem es nicht das letzte Zeichen des Suchstrings betrifft. Deshalb kann der gesamte Suchstring nur bis eine Stelle nach dem gefundenen Mismatch verschoben werden.

<td>A

</td>

<td>B

</td>

<td>R

</td>

<td>A

</td>

<td>G

</td>

<td>A

</td>

<td>D

</td>

<td>A

</td>

<td>B

</td>

<td>R

</td>

<td>A

</td>

<td>K

</td>

<td>A

</td>

<td>D

</td>

<td>A

</td>

<td>B

</td>

<td>R

</td>

<td>A

</td></tr>

<tr>

<td>A

</td>

<td>B

</td>

<td>R

</td>

<td>A

</td>

<td>K

</td>

<td>A

</td>

<td>D

</td>

<td>A

</td>

<td>B

</td>

<td>R

</td>

<td>A

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>A

</td>

<td>B

</td>

<td>R

</td>

<td>A

</td>

<td>K

</td>

<td>A

</td>

<td>D

</td>

<td>A

</td>

<td>B

</td>

<td>R

</td>

<td>A

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>A

</td>

<td>B

</td>

<td>R

</td>

<td>A

</td>

<td>K

</td>

<td>A

</td>

<td>D

</td>

<td>A

</td>

<td>B

</td>

<td>R

</td>

<td>A

</td></tr></tbody></table>

Skip-Tabelle für das oben aufgeführte Beispiel:

<td>A

</td>

<td>B

</td>

<td>R

</td>

<td>K

</td>

<td>D

</td></tr>

<tr>

<td>0

</td>

<td>2

</td>

<td>1

</td>

<td>6

</td>

<td>4

</td></tr></tbody></table>

Der Boyer-Moore-Algorithmus arbeitet am effizientesten, wenn er ein Zeichen vorfindet, das im Suchmuster nicht vorkommt. Die Bad-Character-Regel kommt dann zum Tragen. Dies ist sehr wahrscheinlich bei einem relativ kleinen Muster und einem großen Alphabet, was ihn für einen solchen Fall besonders geeignet macht. In diesem Fall arbeitet der Algorithmus mit einer Effizienz von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left({\frac {n}{m}}\right)}">

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left({\frac {n}{m}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/129320d644799f7990a00719066b69231521761e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:7.812ex; height:4.843ex;" alt="{\displaystyle O\left({\frac {n}{m}}\right)}" loading="lazy"> Vergleichen.

<div class="mw-heading mw-heading3"><h3 id="Good-Suffix-Heuristik">Good-Suffix-Heuristik</h3></div>

String: reinesupersauersupesupersupe

Suchmuster: supersupe